home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / ncmp424s.zoo / compress42.c < prev    next >
C/C++ Source or Header  |  1993-03-06  |  49KB  |  1,946 lines
  1. /* (N)compress42.c - File compression ala IEEE Computer, Mar 1992.
  2.  *
  3.  * Authors:
  4.  *   Spencer W. Thomas   (decvax!harpo!utah-cs!utah-gr!thomas)
  5.  *   Jim McKie           (decvax!mcvax!jim)
  6.  *   Steve Davies        (decvax!vax135!petsd!peora!srd)
  7.  *   Ken Turkowski       (decvax!decwrl!turtlevax!ken)
  8.  *   James A. Woods      (decvax!ihnp4!ames!jaw)
  9.  *   Joe Orost           (decvax!vax135!petsd!joe)
  10.  *   Dave Mack           (csu@alembic.acs.com)
  11.  *   Peter Jannesen, Network Communication Systems
  12.  *                       (peter@ncs.nl)
  13.  *
  14.  * Revision 4.2.3  92/03/14 peter@ncs.nl
  15.  *   Optimise compress and decompress function and a lot of cleanups.
  16.  *   New fast hash algoritme added (if more than 800Kb available).
  17.  *
  18.  * Revision 4.1  91/05/26 csu@alembic.acs.com
  19.  *   Modified to recursively compress directories ('r' flag). As a side
  20.  *   effect, compress will no longer attempt to compress things that
  21.  *   aren't "regular" files. See Changes.
  22.  *
  23.  * Revision 4.0  85/07/30  12:50:00  joe
  24.  *   Removed ferror() calls in output routine on every output except first.
  25.  *   Prepared for release to the world.
  26.  * 
  27.  * Revision 3.6  85/07/04  01:22:21  joe
  28.  *   Remove much wasted storage by overlaying hash table with the tables
  29.  *   used by decompress: tab_suffix[1<<BITS], stack[8000].  Updated USERMEM
  30.  *   computations.  Fixed dump_tab() DEBUG routine.
  31.  *
  32.  * Revision 3.5  85/06/30  20:47:21  jaw
  33.  *   Change hash function to use exclusive-or.  Rip out hash cache.  These
  34.  *   speedups render the megamemory version defunct, for now.  Make decoder
  35.  *   stack global.  Parts of the RCS trunks 2.7, 2.6, and 2.1 no longer apply.
  36.  *
  37.  * Revision 3.4  85/06/27  12:00:00  ken
  38.  *   Get rid of all floating-point calculations by doing all compression ratio
  39.  *   calculations in fixed point.
  40.  *
  41.  * Revision 3.3  85/06/24  21:53:24  joe
  42.  *   Incorporate portability suggestion for M_XENIX.  Got rid of text on #else
  43.  *   and #endif lines.  Cleaned up #ifdefs for vax and interdata.
  44.  *
  45.  * Revision 3.2  85/06/06  21:53:24  jaw
  46.  *   Incorporate portability suggestions for Z8000, IBM PC/XT from mailing list.
  47.  *   Default to "quiet" output (no compression statistics).
  48.  *
  49.  * Revision 3.1  85/05/12  18:56:13  jaw
  50.  *   Integrate decompress() stack speedups (from early pointer mods by McKie).
  51.  *   Repair multi-file USERMEM gaffe.  Unify 'force' flags to mimic semantics
  52.  *   of SVR2 'pack'.  Streamline block-compress table clear logic.  Increase 
  53.  *   output byte count by magic number size.
  54.  * 
  55.  * Revision 3.0   84/11/27  11:50:00  petsd!joe
  56.  *   Set HSIZE depending on BITS.  Set BITS depending on USERMEM.  Unrolled
  57.  *   loops in clear routines.  Added "-C" flag for 2.0 compatibility.  Used
  58.  *   unsigned compares on Perkin-Elmer.  Fixed foreground check.
  59.  *
  60.  * Revision 2.7   84/11/16  19:35:39  ames!jaw
  61.  *   Cache common hash codes based on input statistics; this improves
  62.  *   performance for low-density raster images.  Pass on #ifdef bundle
  63.  *   from Turkowski.
  64.  *
  65.  * Revision 2.6   84/11/05  19:18:21  ames!jaw
  66.  *   Vary size of hash tables to reduce time for small files.
  67.  *   Tune PDP-11 hash function.
  68.  *
  69.  * Revision 2.5   84/10/30  20:15:14  ames!jaw
  70.  *   Junk chaining; replace with the simpler (and, on the VAX, faster)
  71.  *   double hashing, discussed within.  Make block compression standard.
  72.  *
  73.  * Revision 2.4   84/10/16  11:11:11  ames!jaw
  74.  *   Introduce adaptive reset for block compression, to boost the rate
  75.  *   another several percent.  (See mailing list notes.)
  76.  *
  77.  * Revision 2.3   84/09/22  22:00:00  petsd!joe
  78.  *   Implemented "-B" block compress.  Implemented REVERSE sorting of tab_next.
  79.  *   Bug fix for last bits.  Changed fwrite to putchar loop everywhere.
  80.  *
  81.  * Revision 2.2   84/09/18  14:12:21  ames!jaw
  82.  *   Fold in news changes, small machine typedef from thomas,
  83.  *   #ifdef interdata from joe.
  84.  *
  85.  * Revision 2.1   84/09/10  12:34:56  ames!jaw
  86.  *   Configured fast table lookup for 32-bit machines.
  87.  *   This cuts user time in half for b <= FBITS, and is useful for news batching
  88.  *   from VAX to PDP sites.  Also sped up decompress() [fwrite->putc] and
  89.  *   added signal catcher [plus beef in write_error()] to delete effluvia.
  90.  *
  91.  * Revision 2.0   84/08/28  22:00:00  petsd!joe
  92.  *   Add check for foreground before prompting user.  Insert maxbits into
  93.  *   compressed file.  Force file being uncompressed to end with ".Z".
  94.  *   Added "-c" flag and "zcat".  Prepared for release.
  95.  *
  96.  * Revision 1.10  84/08/24  18:28:00  turtlevax!ken
  97.  *   Will only compress regular files (no directories), added a magic number
  98.  *   header (plus an undocumented -n flag to handle old files without headers),
  99.  *   added -f flag to force overwriting of possibly existing destination file,
  100.  *   otherwise the user is prompted for a response.  Will tack on a .Z to a
  101.  *   filename if it doesn't have one when decompressing.  Will only replace
  102.  *   file if it was compressed.
  103.  *
  104.  * Revision 1.9  84/08/16  17:28:00  turtlevax!ken
  105.  *   Removed scanargs(), getopt(), added .Z extension and unlimited number of
  106.  *   filenames to compress.  Flags may be clustered (-Ddvb12) or separated
  107.  *   (-D -d -v -b 12), or combination thereof.  Modes and other status is
  108.  *   copied with copystat().  -O bug for 4.2 seems to have disappeared with
  109.  *   1.8.
  110.  *
  111.  * Revision 1.8  84/08/09  23:15:00  joe
  112.  *   Made it compatible with vax version, installed jim's fixes/enhancements
  113.  *
  114.  * Revision 1.6  84/08/01  22:08:00  joe
  115.  *   Sped up algorithm significantly by sorting the compress chain.
  116.  *
  117.  * Revision 1.5  84/07/13  13:11:00  srd
  118.  *   Added C version of vax asm routines.  Changed structure to arrays to
  119.  *   save much memory.  Do unsigned compares where possible (faster on
  120.  *   Perkin-Elmer)
  121.  *
  122.  * Revision 1.4  84/07/05  03:11:11  thomas
  123.  *   Clean up the code a little and lint it.  (Lint complains about all
  124.  *   the regs used in the asm, but I'm not going to "fix" this.)
  125.  *
  126.  * Revision 1.3  84/07/05  02:06:54  thomas
  127.  *   Minor fixes.
  128.  *
  129.  * Revision 1.2  84/07/05  00:27:27  thomas
  130.  *   Add variable bit length output.
  131.  *
  132.  */
  133. #include    <stdio.h>
  134. #include    <fcntl.h>
  135. #include    <ctype.h>
  136. #include    <signal.h>
  137. #include    <sys/types.h>
  138. #include    <sys/stat.h>
  139. #include    <errno.h>
  140.  
  141. #ifdef DIRENT
  142. #    include    <dirent.h>
  143. #    define    RECURSIVE        1
  144. #    undef    SYSDIR
  145. #endif
  146. #ifdef SYSDIR
  147. #    include    <sys/dir.h>
  148. #    define    RECURSIVE        1
  149. #endif
  150. #ifdef UTIME_H
  151. #    include    <utime.h>
  152. #else
  153.     struct utimbuf {
  154.         time_t actime;
  155.         time_t modtime;
  156.     };
  157. #endif
  158.  
  159. #ifdef    __STDC__
  160. #    define    ARGS(a)                a
  161. #else
  162. #    define    ARGS(a)                ()
  163. #endif
  164.  
  165. #define    LARGS(a)    ()    /* Relay on include files for libary func defs. */
  166.  
  167. #ifndef SIG_TYPE
  168. #    define    SIG_TYPE    void (*)()
  169. #endif
  170.  
  171. #ifndef NOFUNCDEF
  172.     extern    void    *malloc    LARGS((int));
  173.     extern    void    free    LARGS((void *));
  174. #ifndef _IBMR2
  175.     extern    int        open    LARGS((char const *,int,...));
  176. #endif
  177.     extern    int        close    LARGS((int));
  178.     extern    int        read    LARGS((int,void *,int));
  179.     extern    int        write    LARGS((int,void const *,int));
  180.     extern    int        chmod    LARGS((char const *,int));
  181.     extern    int        unlink    LARGS((char const *));
  182.     extern    int        chown    LARGS((char const *,int,int));
  183.     extern    int        utime    LARGS((char const *,struct utimbuf const *));
  184.     extern    char    *strcpy    LARGS((char *,char const *));
  185.     extern    char    *strcat    LARGS((char *,char const *));
  186.     extern    int        strcmp    LARGS((char const *,char const *));
  187.     extern    unsigned strlen    LARGS((char const *));
  188.     extern    void    *memset    LARGS((void *,char,unsigned int));
  189.     extern    void    *memcpy    LARGS((void *,void const *,unsigned int));
  190.     extern    int        atoi    LARGS((char const *));
  191.     extern    void    exit    LARGS((int));
  192.     extern    int        isatty    LARGS((int));
  193. #endif
  194.     
  195. #define    MARK(a)    { asm(" .globl M.a"); asm("M.a:"); }
  196.  
  197. #ifdef    DEF_ERRNO
  198.     extern int    errno;
  199. #endif
  200.  
  201. #include "patchlevel.h"
  202.  
  203. #undef    min
  204. #define    min(a,b)    ((a>b) ? b : a)
  205.  
  206. #ifndef    IBUFSIZ
  207. #    define    IBUFSIZ    BUFSIZ    /* Defailt input buffer size                            */
  208. #endif
  209. #ifndef    OBUFSIZ
  210. #    define    OBUFSIZ    BUFSIZ    /* Default output buffer size                            */
  211. #endif
  212.  
  213. #define MAXPATHLEN 1024        /* MAXPATHLEN - maximum length of a pathname we allow     */
  214. #define    SIZE_INNER_LOOP        256    /* Size of the inter (fast) compress loop            */
  215.  
  216.                             /* Defines for third byte of header                     */
  217. #define    MAGIC_1        (char_type)'\037'/* First byte of compressed file                */
  218. #def